package answer_1_10

import "fmt"

//给你一个字符串 s，找到 s 中最长的 回文 子串 。

//示例 1：
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。

//示例 2：
//输入：s = "cbbd"
//输出："bb"

//提示：
//1 <= s.length <= 1000
//s 仅由数字和英文字母组成

func Answer_5() {
	fmt.Println(longestPalindrome_1("babad"))
}

func longestPalindrome_1(s string) string {
	if len(s) < 2 {
		return s
	}
	left := 0
	right := 0
	maxLen := 0
	for i := 0; i < len(s); i++ {
		for j := i; j < len(s); j++ {
			if s[i] == s[j] {
				if j-i > maxLen {
					if isOk(s, i, j) {
						maxLen = j - i
						left = i
						right = j
					}
				}
			}
		}
	}
	return s[left : right+1]
}

func isOk(s string, left int, right int) bool {
	for left < right {
		if s[left] != s[right] {
			return false
		}
		left++
		right--
	}
	return true
}

func longestPalindrome_2(s string) string {
	n := len(s)
	dp := make([][]bool, n)
	for i, _ := range dp {
		dp[i] = make([]bool, n)
	}
	ans := ""
	for l := 0; l < n; l++ { // l为本次循环遍历的子串长度
		for i := 0; i+l < n; i++ {
			j := i + l
			if l == 0 {
				dp[i][j] = true
			} else if l == 1 {
				dp[i][j] = (s[i] == s[j])
			} else {
				dp[i][j] = (s[i] == s[j] && dp[i+1][j-1])
			}
			if dp[i][j] && l+1 > len(ans) {
				ans = s[i : j+1]
			}
		}
	}
	return ans
}
